package 编辑距离;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/20 10:44
 * @description:
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 示例 1：
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
 * 示例 2：
 * 输入：word1 = "intention", word2 = "execution"
 * 输出：5
 * 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
 * 提示：
 * 0 <= word1.length, word2.length <= 500
 * word1 和 word2 由小写英文字母组成
 */
public class Solution {
    public int minDistance(String word1, String word2) {
        // 二维动态规划：
        // ① dp数组及其下标含义：dp[i][j]表示word1中以下标 j-1 结尾的子串，word2中以下标 j-1 结尾的子串，子串相等的最小操作数
        // ② 状态转移方程：if(wrod1[j-1] == word2[i-1]) dp[i][j] = dp[i-1][j-1]
        //              else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
        // ③ dp数组的初始化：当i=0时，可以理解为需要删除word1中的每一个字符: dp[0][j] = j;
        //                  当j=0时，可以理解为需要插入word2中的每一个字符：dp[i][0] = i;
        // ④ 遍历方向：从状态转移方程不难看出，是从左上角到右下角的
        // ⑤ 举例推导dp数组：输入：word1 = "horse", word2 = "ros"
        //                index:    0   h   o   r   s   e
        //                   0      0   1   2   3   4   5
        //                   r      1   1   2   2   3   4
        //                   o      2   2   1   2   3   4
        //                   s      3   3   2   2   2   3


        int word1Len = word1.length();
        int word2Len = word2.length();

        int[][] dp = new int[word2Len + 1][word1Len + 1];
        // init dp
        for (int i = 0; i <= word1Len; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i <= word2Len; i++) {
            dp[i][0] = i;
        }
        System.out.println(Arrays.toString(dp[0]));
        // Traversal word2 by row
        for (int i = 1; i <= word2Len; i++) {
            // Traversal word1 by cloumn
            for (int j = 1; j <= word1Len; j++) {
                if (word2.charAt(i - 1) == word1.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 找操作最小，依次是：增 dp[i - 1][j]，删 dp[i][j - 1]，替换 dp[i - 1][j - 1]
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }

        return dp[word2Len][word1Len];
    }
}
